package com.itheima.leetcode.od.c.bf;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

/**
 * <h3>排队游戏</h3>
 */
public class QueueGame {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 班级总人数
        int n = sc.nextInt();
        // 刺头人数
        int m = sc.nextInt();
        // 最大不满程度
        int k = sc.nextInt();

        // 刺头所在位置
        HashSet<Integer> pricks_idx = new HashSet<>();
        for (int i = 0; i < m; i++) {
            pricks_idx.add(sc.nextInt());
        }

        // 总不满意程度
        int unHappy = 0;

        // 记录所有刺头的能力
        ArrayList<Integer> pricks = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // 当前学生能力
            int ability = sc.nextInt();

            // 当前学生能力在刺头中的排名, 这里使用二分查找pricks中最后一个等于ability的位置，如果pricks中没有等于ability的值，则返回第一个大于ability的位置
            int rank = searchRightmost(pricks, ability);

            if (rank < 0) {
                rank = -rank - 1;
            } else {
                rank += 1;
            }

            if (pricks_idx.contains(i)) {
                // 如果当前学生是刺头，那么就（有序）插入到刺头学生中
                pricks.add(rank, ability);
            } else {
                // 如果当前学生是非刺头，那么 [rank ~ pricks.size() - 1] 范围的所有刺头学生都是能力值比当前学生高的
                unHappy += pricks.size() - rank;
            }
        }

        System.out.println(unHappy > k ? 1 : 0);
    }

    public static int searchLast(ArrayList<Integer> list, int target) {
        int low = 0;
        int high = list.size() - 1;

        while (low <= high) {
            int mid = (low + high) >> 1;
            int midVal = list.get(mid);

            if (midVal > target) {
                high = mid - 1;
            } else if (midVal < target) {
                low = mid + 1;
            } else {
                // 向右延伸判断，mid是否为target数域的右边界，即最后一次出现的位置
                if (mid == list.size() - 1 || list.get(mid) - list.get(mid + 1) != 0) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }

        return -low - 1; // 找不到则返回插入位置
    }

    public static int searchRightmost(ArrayList<Integer> list, int target) {
        int low = 0;
        int high = list.size() - 1;

        while (low <= high) {
            int mid = (low + high) >> 1;
            int midVal = list.get(mid);

            if (midVal > target) {
                high = mid - 1;
            } else { // 右边界
                low = mid + 1;
            }
        }

        return -low - 1; // 找不到则返回插入位置
    }
}